Abstract: We discuss some different combinatorial ways in which two classes of permutations might resemble each other. We'll focus on parallels between involutions in the symmetric group and the symmetric group as a whole, in particular parallels related to pattern avoidance. We'll also suggest some related interesting questions.
Abstract: We discuss some different combinatorial ways in which two classes of permutations might resemble each other. We'll focus on parallels between involutions in the symmetric group and the symmetric group as a whole, in particular parallels related to pattern avoidance. We'll also suggest some related interesting questions.
Wednesday, November 11th
Linh Tran, Rutgers University
"The Combinatorics of Random Boxes"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: Consider a set of $n$ random axis parallel boxes in the unit hypercube
in $R^d$, where $d$ is fixed and $n$ tends to infinity, with some
overlaps here and there. What is the most economic way to shoot all the
boxes, i.e. with the minimal amount of bullets? In the talk I will show
you how to attack the problem using several tools and tricks from
probabilistic combinatorics. There will also be a very bold (and still
open) conjecture for someone who like a challenge!
Wednesday, November 4th
Brian Thompson, Rutgers University
"My Problem is Harder Than Yours: Complexity Theory for the Combinatorialist"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract:
A spaceship lands in the Mathematics Graduate Student Lounge during
Pizza Seminar one day. An evil-looking alien hops out and threatens to
destroy all of Hill Center next year unless we solve one of two problems:
1) Solve an order-n Sudoku puzzle.
2) Determine whether two graphs on n vertices are isomorphic.
We get to choose the problem, then the alien will give us the hardest
example he/she/it can conjure. Which should we choose?
Oddly enough, there's a whole field of theoretical computer science
devoted to answering these kinds of questions. We will discuss the idea
of reduction, a key concept in Complexity Theory, and use it to compare
the relative difficulties of various combinatorial problems.
Wednesday, October 28th
Andrew Baxter, Rutgers University
"Using the cluster method to enumerate generalized permutation patterns"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: In 2000, Babson and Steingrimsson introduced generalized permutation patterns, with definitions general enough to apply to words on n letters. Using the cluster method, we develop recurrences which count words according to the number of occurrences of certain generalized permutation patterns. From this we can determine qualities such as equidistribution and packing densities.
Wednesday, October 21st
Wes Pegden, Rutgers University
"The Local Lemma and its Applications"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract:
The Lovasz Local Lemma is a power tool in probabilistic combinatorics. In contrast to simpler probabilistic proof techniques, the Local Lemma allows probabilistic proofs for the existence of even very rare combinatorial objects. In this talk, I will state and "interpret" the Local Lemma, and show how it can be applied in a variety of situations. I will also discuss some common pitfalls (we will "prove" that a triangle can be 2-colored). Time permitting, I will talk some about my research on applications of the Local Lemma to games.
Wednesday, October 14th
Emilie Hogan, Rutgers University
"Recurrences that Generate Surprising Numbers"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: The most basic type of recurrence is a linear recurrence (e.g.,
Fibonacci). These types of recurrences generate integers, but this is not
surprising. In order to get integers in an unexpected way you must
consider non-linear recurrences. A well known example of a non-linear
recurrence is the Somos-4 recurrence. In order to get the n^th number in
the sequence you must take some combination of the n-1st, n-2nd, and n-3rd
numbers and then *divide* by the n-4th number. Even though we divide, we
still get integers. I will talk about this phenomenon generally and give a
few other examples. Finally I will introduce the concept of a recurrence
that does not generate a sequence, but instead generates multiple values
at each step by solving a degree n polynomial. In this situation it
becomes surprising that we generate rational numbers.
Wednesday, October 7th
Hoi Nguyen, Rutgers University
"A detour on the Littlewood-Offord theorem"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: Several classical results on the L-O problems will be
discussed. We then introduce a new perspective. Applications will be
included if time permits.
Wednesday, September 30th
Brian Nakamura, Rutgers University
"Graph Pebbling"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: Graph pebbling is a simple notion: scatter some pebbles onto the vertices of a connected graph and if there are at least 2 pebbles on the same vertex, we can remove one pebble and move the other pebble to a neighbor of that vertex. From this though, a number of interesting questions can be asked. This talk will provide a brief overview of some of those problems and a few interesting results.
Wednesday, September 23rd
Ke Wang, Rutgers University
"A quick introduction to Spectral Graph Theory"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: Spectral graph theory is concerned with the eigenvalues and
eigenvectors of matrices associated with graphs (Laplacian matrix,
adjacency matrix, etc), and their application. In this talk, I will
introduce the Laplacian matrix, discuss some basic facts about the
spectrum of a graph, and survey some older and newer results in the end.
Wednesday, September 16th
Humberto Montalvan, Rutgers University
"A Proof of the Erdos-Stone Theorem"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: In this talk I will show how one can prove the celebrated Erdos-Stone theorem using Szemeredi's regularity lemma.
Time permitting, I will discuss an intriguing application of the theorem.
Wednesday, September 9th
Robert DeMarco, Rutgers University
"Applications of Graph Theory: Disease Spread and More"
Time: 12:10 PM
Location: Hill Grad Student Lounge
Abstract: This talk will introduce the use of graphs in modeling of
disease spread and vaccination. Similar models can also be used to help
study crystal growth, forest fire-fighting and public opinion. I will
note a few results in these areas, from the very real-world applicable
to the completely non applicable yet beautiful. To ease us into the
semester, the focus will be on stating and motivating pretty theorems
and not on technical details.
A few things - due to some scheduling conflicts, I'm going to change our
starting time to 12:10pm each week. I've had 12:00 on my website, but
I'm in the process of changing that there as well.
This page was last updated on September 16, 2009 at 12:37 pm and is maintained by webmaster@math.rutgers.edu.
